package greedyAlgorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

public class fourSum {
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list=new ArrayList<>();
        //排序
        Arrays.sort(nums);
        for (int i = 0; i <nums.length ; ) {
            long ret=(long)target-nums[i];
            //三位数之和：
            for (int j = i+1; j <nums.length ; ) {
                int left=j+1;
                int right=nums.length-1;
                while (left<right){
                    long sum=(long) nums[j]+nums[left]+nums[right] ;
                    if(sum>ret){
                        right--;
                    }else if(sum<ret){
                        left++;
                    }else {
                        list.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        left++;
                        right--;
                        while (left<right&&nums[left]==nums[left-1]){
                            left++;
                        }
                        while (left<right&&nums[right]==nums[right+1]){
                            right--;
                        }
                    }
                }
                j++;
                while (j<nums.length&&nums[j]==nums[j-1]){
                    j++;
                }
            }
            i++;
            while (i<nums.length&&nums[i]==nums[i-1]){
                i ++;
            }
        }
        return list;
    }

    public static void main(String[] args) {
        int[] arrays={1,0,-1,0,-2,2};
        // 1. 先获取四数之和的结果列表（List<List<Integer>>）
        List<List<Integer>> result=fourSum(arrays,0);
        Iterator<List<Integer>> iterator=result.iterator();
        while (iterator.hasNext()){
            List<Integer> druple=iterator.next();
            System.out.println(druple);
        }

    }
}
